/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.algorithm.heuristic;

import java.util.PriorityQueue;

import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;

/**
 * @author minho kim
 *
 */
public class GreedySearchHeuristic implements HeuristicAlgorithm {
	private Heuristic heuristic = new Heuristic();
	private CityPath cityPath;
	
	/* (non-Javadoc)
	 * @see kaist.sep502.tsp.algorithm.heuristic.HeuristicAlgorithm#getHx(kaist.sep502.tsp.model.CityPath)
	 */
	@Override
	public Heuristic getHx(CityPath cityPath) {
		this.heuristic.hx = 0.0;
		this.heuristic.cityNo = Problem.getGoalCityNo();
		this.cityPath = cityPath;
		
		if(cityPath.index == Problem.getCitySize()){
			return heuristic;
		}
		
		setHeuristic();
		
		return heuristic;
	}
	
	/* (non-Javadoc)
	 * @see kaist.sep502.tsp.algorithm.heuristic.HeuristicAlgorithm#getHx(kaist.sep502.tsp.model.CityPath, int)
	 */
	@Override
	public Heuristic getHx(CityPath cityPath, int nextCityNo) {
		this.heuristic.hx = 0.0;
		this.heuristic.cityNo = nextCityNo;
		this.cityPath = cityPath;
		
		if(cityPath.index == Problem.getCitySize()){
			return heuristic;
		}
		
		setHeuristic(nextCityNo);
		
		return heuristic;
	}

	protected void setHeuristic(){
		PriorityQueue<CityPath> minimumSpanningTree = new PriorityQueue<CityPath>();
		
		boolean noNeed = false;
		for(int i=0; i<Problem.getCitySize(); i++){
			noNeed = false;
			for(int j=0; j<cityPath.index; j++){
				if(i == cityPath.tourHistory[j]){
					noNeed = true;
					break;
				}
			}
			if(noNeed){
				continue;
			}
			minimumSpanningTree.add(getMinimalSpanningCityPath(i, Problem.getGoalCityNo()));
		}
		
		CityPath bestOne = minimumSpanningTree.poll();
		heuristic.cityNo = bestOne.tourHistory[1];
		heuristic.hx = bestOne.hx;
	}
	
	protected void setHeuristic(int nextCityNo){
		CityPath bestOne = getMinimalSpanningCityPath(nextCityNo, Problem.getGoalCityNo());
		heuristic.hx = bestOne.hx;
	}
	
	/**
	 * return one citypath that has all route from baseCityPath to 'to'(usually goalCity)
	 * this is for g(from) and h(from)
	 *  
	 * @param baseCityPath : current City Path
	 * @param from : next route for traveling
	 * @param to : goal city
	 * @return CityPath : Path = baseCity ~ from; g(x) = baseCity ~ from; h(x) = from ~ to  
	 */
	protected CityPath getMinimalSpanningCityPath(int from, int to) {
		int[] exceptPath = cityPath.tourHistory;
		int baseCityNo = cityPath.getLastCity();
		
		CityPath cityPath = new CityPath(baseCityNo);
		double gx = Problem.getDistance(baseCityNo, from);
		double hx = 0.0;
		cityPath.set(from, hx); cityPath.gx = gx; // force to set gx value (baseCity ~ from) 
		int currentCityNo = from;
		
		do {
			from = currentCityNo; // temporary
			currentCityNo = Problem.getClosestCityNoAdvanced(currentCityNo, cityPath.tourHistory, exceptPath);
			
			if(currentCityNo == -1){ // if it can't find the closest city, it means it travled all cities.
				currentCityNo = to;
			}
			
			hx = cityPath.hx + Problem.getDistance(from, currentCityNo);
			cityPath.set(currentCityNo, hx); cityPath.gx = gx; // froce to set gx value (baseCity ~ from)
		} while(currentCityNo != to);
		
		return cityPath;
	}
	
	
	/**
	 * return one citypath that has all route from baseCityPath to 'to'(usually goalCity)
	 *  
	 * @param baseCityPath : current City Path
	 * @param from : next route for traveling
	 * @param to : goal city
	 * @return
	 */
	protected CityPath getMinimalSpanningCityPath1(CityPath baseCityPath, int from, int to) {
		int[] exceptPath = baseCityPath.tourHistory;
		int baseCityNo = baseCityPath.getLastCity();
		
		CityPath cityPath = new CityPath(baseCityNo);
		double hx = Problem.getDistance(baseCityNo, from);
		cityPath.set(from, hx); 
		int currentCityNo = from;
		
		do {
			from = currentCityNo; // temporary
			currentCityNo = Problem.getClosestCityNoAdvanced(currentCityNo, cityPath.tourHistory, exceptPath);
			
			if(currentCityNo == -1){ // if it can't find the closest city, it means it travled all cities.
				currentCityNo = to;
			}
			
			hx = cityPath.hx + Problem.getDistance(from, currentCityNo);
			cityPath.set(currentCityNo, hx);
		} while(currentCityNo != to);
		
		return cityPath;
	}

}
